//
//  list.hpp
//  list
//
//  Created by chenyh on 2021/2/4.
//

#ifndef list_hpp
#define list_hpp

#include <iostream>
/**
 https://www.cnblogs.com/fengyhack/p/10603677.html
 使用模版时 建议将模版的声明和实现都在一个文件中完成
 1-因为在编译阶段并未生成具体二进制代码
2- 在编译阶段只发现了testfunc的引用，但是在main.obj中并没有相关的可执行代码
 这就是为什么需要链接也就是link了。在main中虽然引用到testfunc但是只提供了一个call
 虚拟地址二没有实际的执行代码
 3- 链接阶段将各个模块（编译期间生成的很多*。obj文件）组织起来，
 在main中从调用处jump到这里即可。执行完毕再跳出子模块。从中断点继续执行后续语句
 
 4-模版在编译期间是不生成具体代码的，除非有特化的引用
 
 那么，如何解决这个问题呢？

 至少有以下几种方法：

 1、在一个文件中完成模板的声明及实现

 2、在模板头文件末尾添加实现文件的包含 #include "MyTemnplate.cpp"

 3、在调用方(main.cpp中)包含实现文件 #include "MyTemnplate.cpp"
 
 第二种方式还不如第一种方式简洁，实际上就是一个东西，

 第三种方法可能会造成而外开销（比如多个模块都调用了这个模板的某个特化实例的

 情形）

 但一般来说这种开销不算什么，除非你的要求很严格，那么请采用第一种方式吧
 事实上，除了模板，抽象类等也不能被实例化，在这种情况下，建议采用上述的

 第一种方法：

 在一个文件中完成模板的声明及实现
 */
/*********线性表数据结构*******/
const int defaultsize = 10; //设置默认顺序表大小
template <typename DataType>
class SeqList {
public:
    SeqList(int size=defaultsize) {
        if (size > 0) {
            maxSize = size;
            length = 0;
            elements = new DataType(maxSize); //分配内存大小
            for (int i = 0; i < maxSize; i++) {
                elements[i] = NULL;
            }
        }
    }
    //析构函数
    ~SeqList()
    {
        delete [] elements;                  //回收内存空间
    }
    
    bool insertElement(DataType data);       //向表尾插入新元素
    bool deleteElement(int location);        //删除指定位置的元素
    DataType getElement(int location);       //返回指定位置的元素
    bool  changeElement(int location,DataType newData);//修改指定位置的元素值
    int   getLenght();                       //获取顺序表有效长度
    
private:
    DataType *elements;
    int maxSize;                            //顺序表最大大小
    int length;                             //顺序表的有效长度
};



/// 顺序表的插入操作
/// @param data 新元素

template <typename DataType>
bool SeqList<DataType>::insertElement(DataType data)
{
    int currentIndex = length;          //记录新元素的插入位置
    if (length >= maxSize) {            //判断顺序表是否已满
        return false;                   //顺序表已满，返回false，插入不成功
    }
    else
    {
        elements[currentIndex] = data;  //将新元素插入顺序表表尾
        length++;                       //顺序表有效长度加1；
        return false;
    }
}

template <typename DataType>
/// 删除顺序表指定元素
/// @param location 顺序表指定元素的位置索引
bool SeqList<DataType>::deleteElement(int location) {
    if (location >= length || length < 0) { //验证位置索引参数是否有效
        return false;
    }
    else
    {
        for (int i=location; i < length; i++) {
            elements[i] = elements[i+1]; //将指定位置之后的元素依次往前移动覆盖前一个元素
        }
        length--;//顺序表长度减1
        return true;
    }
}


template <typename DataType>
/// 获取顺序表指定位置索引的元素
/// @param location 指定位置索引
DataType SeqList<DataType>:: getElement(int location) {
    if (location < 0 || location > length) { //判断位置索引是否合法
        std::cout<<"参数无效"<<std::endl;
        return 0;
    }
    else
    {
        return elements[location];
    }
}
template <typename DataType>
/// 修改指定位置索引的元素
/// @param location 指定位置索引
/// @param newData 新的元素
bool SeqList<DataType>::changeElement(int location, DataType newData)
{
    if (location < 0 || location > length) { //判断位置索引是否合法
        return false;
    }
    else
    {
        elements[location] = newData;
        return true;
    }
    
}

template <typename DataType>
/// 获取顺序表有效长度
int SeqList<DataType>::getLenght()
{
    return length;
}
#endif /* list_hpp */
